\chapter{Solution Approach To Capacity Expansion Problem in Survivable Networks}

\label{chap-three}

In this chapter we first start by providing theoretical insight to the problem and explaining how we reduce the size of the SNCE-1 problem. The result is an integer programming model for any given instance with fewer variables and constraints. Furthermore we introduce some strategies to provide bounds on the objective function. Then by taking advantage of the special structure of the problem, we propose a decomposition approach to the reduced-size problem. The proposed approach will give us the ability to solve larger instances of the problem while maintaining the optimality of the solution.

\section{Feasibility Test}
To be added

\section {Finding All Possible Paths between Two Nodes}

\section{Reduction of Solution Space}

In this section we propose some methods to reduce the number of variables and constraints in instances of SNCE-1 problem, while guaranteeing to keep the optimal solution in the search space. These reductions are expected to contribute to the improvement of solution approach efficiency.


\begin{spacing}{1.5}
\paragraph{Proposition 1}
\textit{ Suppose that for any link $e$, k and m are two possible capacity expansion alternatives with respective costs of $C_{e,k}$ and $C_{e,m}$ and respective capacities of $U_{e,k}$ and $U_{e,m}$. If $C_{e,k} > C_{e,m}$ and $U_{e,k}\leq U_{e,m}$, then the optimal solution to SNCE-1 has ${z^*}_{e,k}=0$ }.

\end{spacing}
\vspace{5mm}
The above proposition says that if among the available capacity expansion alternatives for a link, one of them (say $k$) is suggesting more cost and less (or equal) capacity compared to at least one other alternative, then alternative $k$ will not be chosen to be installed for that link. This proposition can be proven by contradiction.

\paragraph \indent \textit{ \textbf{{Proof :}}} Suppose that for $k$ and $m$ we have

\begin{equation}
C_{e,k} > C_{e,m} \hspace{2mm}and \hspace{2mm} U_{e,k}\leq U_{e,m}
\label{eq:hist0}
\end{equation}
 Let us denote the capacity expansion and flow decisions in a candidate solution with $(\hat{z},\hat{x})$. Suppose we have $\hat{z}_{e,k}=1$ and $\hat{z}_{e,m}=0$. Consider a solution $(\bar{z},\bar{x}) $ which differs from $(\hat{z},\hat{x})$ in such two variables as $\bar{z}_{e,k}=0$ and $\bar{z}_{e,m}=1$. The new solution $(\bar{z},\bar{x}) $ can be expressed in relation to $(\hat{z},\hat{x})$ as follows :

\begin{equation}
  \hat{z}_{i,j} = \bar{z}_{i,j} \hspace{6mm}\forall j\in L_{i} \hspace{4mm} i \in E\setminus\left\{e\right\}
  \label{eq:hist1}
\end{equation}
\begin{equation}
  \hat{z}_{e,j} = \bar{z}_{e,j} \hspace{6mm}\forall j\in L_{e}\setminus\left\{k, m\right\}
  \label{eq:hist2}
\end{equation}
\begin{equation}
  \hat{z}_{e,k} = \bar{z}_{e,m}=1 
  \label{eq:hist3}
\end{equation}
\begin{equation}
  \hat{z}_{e,m} = \bar{z}_{e,k}=0
  \label{eq:hist4}
\end{equation}
\begin{equation}
 \hat{x}_{p_{d},s}=\bar{x}_{p_{d},s} \hspace{2mm} \forall p=1,2,...,|P_{d}| \hspace{2mm} \forall d=1,2,...,|D|; \hspace{2mm} \forall s=1,2,...,|S|
 \label{eq:hist-23}
\end{equation}
We first need to show that given the feasibility of $(\hat{z},\hat{x})$, $(\bar{z},\bar{x})$ is feasible with respect to the constraints of SNCE-1. More precisely we need to show that if
\begin{equation}
 \sum_{l\in l_{e}} \hat{z}_{e,l} \leq 1   \label{eq:hist5}
\end{equation}
and
\begin{equation}
 \lambda_{e,s}\left(U_{e,0} + \sum_{l\in L_{e}}U_{e,l} \hat{z}_{e,l}\right)-\sum_{d\in D}\sum_{p\in P_{d}}k_{e,p_{d}}x_{p_{d},s}\geq 0 \hspace{5mm}  \hspace{2mm} \forall s=1,2,...,|S|  \label{eq:hist6}
\end{equation}
and
\begin{equation}
\sum_{p\in P_{d}}x_{p_{d},s}-\mu_{d,s}h_{d}\geq 0 \hspace{5mm} \forall d=1,2,...,|D| \hspace{2mm} \forall s=1,2,...,|S| \label{eq:hist7}
\end{equation}
are feasible, they will maintain their feasibility using $\bar{z}$ instead of $\hat{z}$. \\

To show the feasibility of $\sum_{i\in l_{e}} \bar{z}_{e,l} \leq 1$, let us re-write equation \ref{eq:hist5} as follows:
\begin{equation}
 \sum_{l\in L_{e}} \hat{z}_{e,l}= \sum_{l\in L_{e}\setminus\left\{k,m\right\}} (\hat{z}_{e,l} + \hat{z}_{e,k}+ \hat{z}_{e,m})\leq 1    \label{eq:hist8}
\end{equation}
 using equations \ref{eq:hist2} to \ref{eq:hist4}, we will have:
 \begin{equation}
 \sum_{l\in L_{e}\setminus\left\{k,m\right\}} (\hat{z}_{e,l} + \hat{z}_{e,k}+ \hat{z}_{e,m})=\sum_{l\in L_{e}\setminus\left\{k,m\right\}} (\bar{z}_{e,l} + \bar{z}_{e,m}+ \bar{z}_{e,k})= \sum_{l\in L_{e}} \bar{z}_{e,l} \leq 1    \label{eq:hist9}
\end{equation}
To prove the feasibility of equation \ref{eq:hist6} %$ \lambda_{e,s}\left(U_{e,0} + \sum_{l\in L_{e}}U_{e,l} \bar{z}_{e,l}\right)-\sum_{d\in D}\sum_{p\in P_{d}}k_{e,p_{d}}\bar{x}_{p_{d},s}\geq 0 \hspace{1mm}  (\forall s=1,2,...,|S|)$% 
we should note that:
\begin{equation}
\sum_{l\in L_{e}}U_{e,l} \hat{z}_{e,l}= \sum_{l\in L_{e}\setminus\left\{k,m\right\}}(U_{e,l} \hat{z}_{e,l}+U_{e,m}\hat{z}_{e,m}+ U_{e,k}\hat{z}_{e,k})  \label{eq:hist10}
\end{equation} using equations \ref{eq:hist3} and \ref{eq:hist4}, the right hand side of equation \ref{eq:hist10} is equal to:
\begin{equation}
 \sum_{l\in L_{e}\setminus\left\{k,m\right\}}(U_{e,l} \hat{z}_{e,l}+U_{e,m}* 0 + U_{e,k}*1) \label{eq:hist12}
\end{equation}
by equation \ref{eq:hist0},
\begin{equation}
 \sum_{l\in L_{e}\setminus\left\{k,m\right\}}(U_{e,l} \hat{z}_{e,l}+U_{e,m}* 0 + U_{e,k}*1) \leq \sum_{l\in L_{e}}(U_{e,l} \hat{z}_{e,l}+U_{e,m}* 1 + U_{e,k}*0) \label{eq:hist13}
\end{equation}
by using equation \ref{eq:hist2} we have
\begin{equation}
\sum_{l\in L_{e}\setminus\left\{k,m\right\}}(U_{e,l} \hat{z}_{e,l}+U_{e,m}* 1 + U_{e,k}*0)=\sum_{l\in L_{e}\setminus\left\{k,m\right\}}(U_{e,l} \bar{z}_{e,l}+U_{e,m}* 1 + U_{e,k}*0)
\label{eq:hist14}
\end{equation}
and by equations \ref{eq:hist3} and \ref{eq:hist4}, the right hand side of equation \ref{eq:hist14} is equal to $\sum_{l\in L_{e}}U_{e,l} \bar{z}_{e,l}$. In other words, in equations \ref{eq:hist10} to \ref{eq:hist14}, we have shown that $ \sum_{l\in L_{e}}U_{e,l} \bar{z}_{e,l}$ is greater than or equal to $\sum_{l\in L_{e}}U_{e,l} \hat{z}_{e,l}$ , leading to the feasibility of equation \ref{eq:hist6} using $ (\bar{z},\hat{x})$ as a solution, given its feasibility by using $(\hat{z},\hat{z})$. Also for the objective function
\begin{equation}
\sum_{a\in E}\sum_{l\in L_{a}}C_{a,l} \hspace{0.5mm}\hat{z}_{a,l}= \sum_{a\in E\setminus\left\{e\right\}}\sum_{l\in L_{a}}(C_{a,l} \hspace{0.5mm}\hat{z}_{a,l} + \sum_{l\in L_{e} \setminus\left\{k,m\right\}} C_{e,l}\hat{z}_{e,l} + C_{e,k}\hat{z}_{e,k} + C_{e,m}\hat{z}_{e,m})
\label{eq:hist15}
\end{equation}
We re-write equation \ref{eq:hist15} using equations \ref{eq:hist1} and \ref{eq:hist2} to get
\begin{equation}
\sum_{a\in E\setminus\left\{e\right\}}\sum_{l\in L_{a}}C_{a,l} \hspace{0.5mm}\bar{z}_{a,l} + \sum_{l\in L_{e} \setminus\left\{k,m\right\}} (C_{e,l}\bar{z}_{e,l} + C_{e,k}\hat{z}_{e,k} + C_{e,m}\hat{z}_{e,m})
\label{eq:hist16}
\end{equation}
by using equations \ref{eq:hist3} and \ref{eq:hist4}
\begin{equation}
\sum_{a\in E\setminus\left\{e\right\}}\sum_{l\in L_{a}}C_{a,l} \hspace{0.5mm}\bar{z}_{a,l} + \sum_{l\in L_{e} \setminus\left\{k,m\right\}} (C_{e,l}\bar{z}_{e,l} + C_{e,k}*1 + C_{e,m}*0)
\label{eq:hist17}
\end{equation}
by equation \ref{eq:hist0}

\begin{eqnarray}
& = & \sum_{a\in E\setminus\left\{e\right\}}\sum_{l\in L_{a}}C_{a,l} \hspace{0.5mm}\bar{z}_{a,l} + \sum_{l\in L_{e} \setminus\left\{k,m\right\}} (C_{e,l}\bar{z}_{e,l} + C_{e,k}*1 + C_{e,m}*0)  \nonumber\\
& > & \sum_{a\in E\setminus\left\{e\right\}} \sum_{l\in L_{a}}C_{a,l} \hspace{0.5mm}\bar{z}_{a,l} + \sum_{l\in L_{e} \setminus\left\{k,m\right\}} (C_{e,l}\bar{z}_{e,l} + C_{e,k}*0 + C_{e,m}*1) \label{eq:hist18}
\end{eqnarray}
by equations \ref{eq:hist3} and \ref{eq:hist4}, we get
\begin{equation}
\sum_{a\in E\setminus\left\{e\right\}}\sum_{l\in L_{a}}C_{a,l} \hspace{0.5mm}\bar{z}_{a,l} + \sum_{l\in L_{e} \setminus\left\{k,m\right\}} ( C_{e,l}\bar{z}_{e,l} + C_{e,k}\bar{z}_{e,k} + C_{e,m}\bar{z}_{e,m})= \sum_{a\in E}\sum_{l\in L_{a}}C_{a,l} \hspace{0.5mm}\bar{z}_{a,l}
\label{eq:hist19}
\end{equation}
which is equal to the objective function of solution $\bar{z}$. In other words, in equations \ref{eq:hist15} to \ref{eq:hist19} we have shown that $f(\bar{z}) < f(\hat{z})$. Therefore the objective value can always be improved by using $\bar{z}$ instead of $\hat{z}$, so $\hat{z}$ cannot be the optimal solution, implying that $z^*_{e,m}=0 $.
\paragraph{Example 1} Recall the introductory example discussed in chapter \ref{chap-two}. For link $e_{3}$ in that example from Table \ref{tab:three} we have:
\begin{equation}
C_{3,1} > C_{3,2} \hspace{3mm} and \hspace{3mm} U_{3,1}\leq U_{3,2} \nonumber
\end{equation}
So the conditions for applying Proposition 1 are being met. Suppose $z_{1}$ is a feasible capacity expansion decision such that $z_{1}=(0,1,1,0,1,0,0,1,0,0)$. $z_{1}$ has $e_{3,1}=1$ and $e_{3,2}=0$. The objective of $z_{1}$, $f(z_{1})$ is equal to 38. Suppose $z_{2}$ is a second solution which is different from $z_{1}$ in only two variables $e_{3,1}$ and $e_{3,2}$; thus $z_{2}=(0,1,1,0,0,1,0,1,0,0)$. By checking $z_{2}$ in the constraints of SNCE-2, it can be observed that $z_{2}$ is also feasible. Also for the objective value $f(z_{6})$ = 36, which shows that  $z_{1}$ cannot be the optimal solution; and therefore $e_{3,1}=0$ in the optimal solution.\\

After applying the results of Proposition 1 to each link, the indices of any remaining variable can be reordered such that  $U_{e,i} \geq U_{e,i+1}$ and $C_{e,i} \geq C_{e,i+1}$ $\forall i\in L_{e}, \forall e\in E$.
% to handle the problem more easily.


\begin{spacing}{1.5}
\paragraph{Proposition 2}
\textit{ If there exist two failure scenarios $\bar{s}$ and $s'$ such that }
\end{spacing}
\begin{equation}
\lambda_{e,\bar{s}} \leq \lambda_{e,s'} \hspace{5mm}\forall e\in E \label{eq:hist20}
\end{equation}
\textit{and}
\begin{equation}
\mu_{d,\bar{s}} \geq \mu_{d,s'} \hspace{5mm}\forall d\in D \label{eq:hist21}
\end{equation}
\textit{then the link capacity and demand constraints representing failure scenario s' will be redundant and can be removed from the model without affecting the optimal solution. }


\vspace{5mm}
The above proposition says that if failure scenario $s'$ is providing link availability of no less than that for $\bar{s}$ on all the links, and has no higher value for any of the demands compared to those for $\bar{s}$, then

\begin{equation}
 \lambda_{e,s'}\left(U_{e,0}+\sum_{l\in L_{e}}U_{e,l}z_{e,l}\right)-\sum_{d\in D}\sum_{p\in P_{d}}k_{e,p_{d}}x_{p_{d},s'}\geq 0 \hspace{5mm} \forall e=1,2,...,|E| \hspace{2mm}  \label{eq:hist22}
\end{equation}
\begin{equation}
\sum_{p\in P_{d}}x_{p_{d},s'}-\mu_{d,s'}h_{d}\geq 0 \hspace{5mm} \forall d=1,2,...,|D| \hspace{2mm}  \label{eq:hist23}
\end{equation}
will be redundant.\\
\\\textit{\textbf{{Proof :}}} To prove the above proposition we need to show that the constraints representing $s'$ are being dominated by the ones representing $\bar{s}$. To do so, we show that any feasible solution for $\bar{s}$ constraints is also feasible for $s'$. Suppose ($ \bar{x}_{p_{d},\bar{s}}, \bar{z}$) are first and second stage feasible solutions with respect to
\begin{equation}
 \lambda_{e,\bar{s}}\left(U_{e,0}+\sum_{l\in L_{e}}U_{e,l}\bar{z}_{e,l}\right)-\sum_{d\in D}\sum_{p\in P_{d}}k_{e,p_{d}}\bar{x}_{p_{d},\bar{s}}\geq 0 \hspace{5mm} \forall e=1,2,...,|E| \hspace{2mm}  \label{eq:hist24}
\end{equation}
\begin{equation}
\sum_{p\in P_{d}}\bar{x}_{p_{d},\bar{s}}-\mu_{d,\bar{s}}h_{d}\geq 0 \hspace{5mm} \forall d=1,2,...,|D| \hspace{2mm}  \label{eq:hist25}
\end{equation}
By using equation \ref{eq:hist21}, we get
\begin{equation}
\sum_{p\in P_{d}}\bar{x}_{p_{d},\bar{s}}-\mu_{d,s'}h_{d}\geq 0 \hspace{5mm} \forall d=1,2,...,|D| \hspace{2mm}  \label{eq:hist26}
\end{equation}
This means that $ \bar{x}_{p_{d},\bar{s}}$ is feasible to the demand constraint for $s'$. Further, from having the feasibility of equation \ref{eq:hist24} and by using equation \ref{eq:hist20},


\begin{eqnarray}
& & \lambda_{e,s'}\left(U_{e,0}+\sum_{l\in L_{e}}U_{e,l}\bar{z}_{e,l}\right)-\sum_{d\in D}\sum_{p\in P_{d}}k_{e,p_{d}}\bar{x}_{p_{d},\bar{s}} \hspace{2mm}  \label{eq:hist27}\\
& \geq &  \lambda_{e,\bar{s}}\left(U_{e,0}+\sum_{l\in L_{e}}U_{e,l}\bar{z}_{e,l}\right)-\sum_{d\in D}\sum_{p\in P_{d}}k_{e,p_{d}}\bar{x}_{p_{d},\bar{s}}\geq 0 \hspace{5mm} \forall e=1,2,...,|E| \hspace{2mm} \nonumber
\end{eqnarray} showing that ($ \bar{x}_{p_{d},\bar{s}}, \bar{z}$) are also feasible for link capacity constraints for the $s'$ scenario. From equations \ref{eq:hist26} and \ref{eq:hist27} it can be inferred that any feasible solution to $\bar{s}$ is also feasible to $s'$, i.e, demand and link capacity constraints of $s'$ are redundant due to being dominated by $\bar{s}$ constraints; and thus they can be removed from the model without affecting the optimal solution.

\paragraph{Example 2} For the failure scenario $s_{1}$ in the introductory example in chapter \ref{chap-two} , $\lambda_{e,s_{1}}=(0.25,1,0.5,0.8,1)$\hspace{3mm} \text{and} \hspace{3mm} $\mu_{d,s_{1}}=(0.5,1.5)$.
Define a second failure scenario $s_{2}$ with $\lambda_{e,s_{2}}=(0.35,1,0.75,0.9,1)$\hspace{3mm} \text{and} \hspace{3mm} $\mu_{d,s_{2}}=(0.4,1.3)$.\\
\indent As $\lambda_{e,s_{1}} \leq \lambda_{e,s_{2}}$ for all $e\in E$ and $\mu_{d,s_{1}} \geq \mu_{d,s_{2}}$ for all $ d\in D $, the conditions for applying Proposition 2 are being met. Therefore we expect the demands and capacity constraints of $s_{2}$ to be dominated by those for $s_{1}$. We first start by comparing the link capacity constraints. Note that we have intentionally left out the scenario index for the flow variables to be able to compare the constraints more easily.
\begin{equation}
e_{1} :
 \begin{cases}
 & 0.25(4+z_{1,1}+3z_{1,1})-(x_{1,1}+x_{2,2}) \geq 0 \hspace{3mm} \text{for $s_{1}$ }  \\
 & 0.35(4+z_{1,1}+3z_{1,1})-(x_{1,1}+x_{2,2}) \geq 0 \hspace{3mm} \text{for $s_{2}$ }  \\
\end{cases}
\end{equation}

$\implies$ The constraint for $s_{1}$ is tighter and dominates the constraint for $s_{2}$. Therefore the constraint from $s_{2}$ can be removed from the model.
\begin{equation}
e_{2} :
 \begin{cases}
 & 3+3z_{2,1}+z_{2,2}-(x_{2,2}+x_{3,2}) \geq 0 \hspace{3mm} \text{for $s_{1}$ }  \\
 & 3+3z_{2,1}+z_{2,2}-(x_{2,2}+x_{3,2}) \geq 0 \hspace{3mm} \text{for $s_{2}$ }  \\
\end{cases}
\end{equation}
$\implies$ The constraints are equal and therefore the one for $s_{2}$ is considered to be redundant and can be removed from the model.
\begin{equation}
e_{3} :
 \begin{cases}
 & 0.5(2+2z_{3,1}+2z_{3,2})-x_{1,2} \geq 0 \hspace{3mm} \text{for $s_{1}$ }  \\
 & 0.75(2+2z_{3,1}+2z_{3,2})-x_{1,2} \geq 0 \geq 0 \hspace{3mm} \text{for $s_{2}$ }  \\
\end{cases}
\end{equation}
$\implies$ The constraint for $s_{1}$ is tighter and dominates the constraint for $s_{2}$. Therefore the constraint for $s_{2}$ can be removed from the model.
\begin{equation}
e_{4} :
 \begin{cases}
 & 0.8(5+5z_{4,1}+2z_{4,2})-x_{3,2} \geq 0 \hspace{3mm} \text{for $s_{1}$ }  \\
 & 0.9(5+5z_{4,1}+2z_{4,2})-x_{3,2} \geq 0 \geq 0 \hspace{3mm} \text{for $s_{2}$ }  \\
\end{cases}
\end{equation}
$\implies$ The constraint for $s_{1}$ is tighter and dominates the constraint for $s_{2}$. Therefore the constraint for $s_{2}$ can be removed from the model.
\begin{equation}
e_{5} :
 \begin{cases}
 & 2+2z_{5,1}+z_{5,2}-x_{2,2} \geq 0 \hspace{3mm} \text{for $s_{1}$ }  \\
 & 2+2z_{5,1}+z_{5,2}-x_{2,2} \geq 0 \geq 0 \hspace{3mm} \text{for $s_{2}$ }  \\
\end{cases}
\end{equation}
$\implies$ The constraints are equal and therefore the one for $s_{2}$ is considered to be redundant and can be removed from the model.\\
As for the demand constraints, the same concept can be shown as follows:
\begin{equation}
d_{1} :
 \begin{cases}
 & x_{1,1}-2 \geq 0 \hspace{3mm} \text{for $s_{1}$ }  \\
 & x_{1,1,1}-1.6 \geq 0 \hspace{3mm} \text{for $s_{2}$ }  \\
\end{cases}
\end{equation}
$\implies$ The constraint for $s_{1}$ is tighter and dominates the constraint for $s_{2}$. Therefore the constraint for $s_{2}$ can be removed from the model.
\begin{equation}
d_{2} :
 \begin{cases}
 & x_{1,2}+x_{2,2}+x_{3,2}-4.5 \geq 0 \hspace{3mm} \text{for $s_{1}$ }  \\
 & x_{1,2}+x_{2,2}+x_{3,2}-3.9 \geq 0 \hspace{3mm} \text{for $s_{2}$ }  \\
\end{cases}
\end{equation}
$\implies$ Again as the constraint for $s_{1}$ is tighter it dominates the constraint for $s_{2}$. Therefore the constraint for $s_{2}$ can be removed from the model.\\



Proposition 2 is specifically important and is expected to contribute to the solution approach efficiency, mainly because once the possible redundant scenarios are found, several variables and constraints can be removed at the same time. To be more precise, for each redundant failure scenario $(|E|+|D|)$ constraints and $ \sum_{d\in D}|P_{d}|$ variables can be removed from the model. This would also result in the reduction of the number of sub-problems in the decomposition algorithm, which will be discussed later. It should be noted that comparing two failure scenarios to identify redundancy or domination requires at most $(|E|+|D|)$ comparisons.




\section{Bounds on the Objective Function  }
In this section we present some  methods to compute lower and upper bounds on the objective function for the SNCE-1 problem. These bounds are expected to provide better insights to the problem. Also they provide estimates of the range of the total cost of investments when exact methods fail to solve the problem and provide the actual cost of capacity expansion decisions to the decision maker.

\subsection{Upper Bounds on the Cost Function}

We start by proposing upper bounds on the objective function.

\paragraph{Lemma 1}
\textit{Suppose Proposition 1 has been applied and the eligible alternatives have been removed. Suppose }
\begin{equation}
U_{e,\hat{l}}=\max_{l\in L_{e}}U_{e,l} \hspace{0.2mm},\hspace{1mm} \forall e \in E
\end{equation}
\textit{and}
\begin{equation}
C_{e,\tilde{l}}=\max_{l\in L_{e}}C_{e,l} \hspace{0.2mm},\hspace{1mm} \forall e \in E
\end{equation}\\
 \textit{Now let $\hat{z}$ and $\tilde{z}$ be first stage feasible solutions with}

\begin{equation}
\hat{z}_{e,\hat{l}}=1 \hspace{4mm}  \forall e \in E,\hspace{1mm} \text{and} \hspace{2mm} \hat{z}_{e,l}=0 \hspace{4mm} \forall l \in L_{e}\setminus\left\{\hat{l}\right\} \hspace{4mm} \forall e \in E
\end{equation}
\begin{equation}
\tilde{z}_{e,\tilde{l}}=1 \hspace{4mm}  \forall e \in E, \hspace{1mm} \text{and} \hspace{2mm} \tilde{z}_{e,l}=0 \hspace{4mm} \forall l \in L_{e}\setminus\left\{\tilde{l}\right\} \hspace{4mm} \forall e \in E
\end{equation}
\textit{Then}
\begin{equation}
\hat{f}=\tilde{f},\hspace{2mm} \text{and}\hspace{2mm} \hat{z}=\tilde{z}\label{eq:hist33}
\end{equation}
\textit{where $\hat{f}=\sum_{e\in E}C_{e,\hat{l}}\hspace{1mm}z_{e,\hat{l}}$ \hspace{1.5mm}} and \hspace{1.5mm} {$\tilde{f}=\sum_{e\in E}C_{e,\tilde{l}}\hspace{1mm}z_{e,\tilde{l}}$} .\\\\

Lemma 1 says that if for all links the highest capacity alternatives are chosen, then results would be the same as choosing the costliest alternatives.\\ \\
\textit{ \textbf{{Proof :}}} The proof is straightforward from the result of Proposition 1: among the remaining alternatives the ones with higher capacities have higher costs as well.
\begin{spacing}{1.5}
\paragraph{Proposition 3}
\textit{Suppose $U_{e,\hat{l}}=\max_{l\in L_{e}}U_{e,l}$ \hspace{0.2mm},\hspace{1mm}$\forall e \in E$. If $\hat{z}$ is a first-stage solution with}
\end{spacing}
\begin{equation}
\hat{z}_{e,l}=0 \hspace{4mm} \forall l \in L_{e}\setminus\left\{\hat{l}\right\} \hspace{4mm} \forall e \in E
\label{eq:hist28}
\end{equation}
\begin{equation}
\hat{z}_{e,\hat{l}}=1 \hspace{4mm}  \forall e \in E \label{eq:hist29}
\end{equation} 
\textit{then if $\hat{z}$ is second-stage infeasible, then the original SNCE-1 problem is infeasible. If $\hat{z}$ is second-stage feasible, then $\hat{f}$, where}

\begin{equation}
\hat{f}=\sum_{e\in E}C_{e,\hat{l}}\hspace{1mm}z_{e,\hat{l}}
\label{eq:hist30}
\end{equation}
\textit{serves as an upper bound for the optimal cost of capacity expansion investments. }


\vspace{5mm}


Proposition 3 suggests that if in the first stage the maximum available capacity is installed for each link, then:
\begin{enumerate}
  \item if the network is not able to find a feasible set of flows under each failure scenario to satisfy the demands, then SNCE-1 problem is infeasible;
  \item if SNCE-1 problem is feasible, then $\hat{f}$ will be an upper bound for the optimal cost of SNCE-1.
\end{enumerate}
\textit{ \textbf{{Proof :}}}
To prove Proposition 3, first recall that a second-stage feasible $z$ is a set of capacity expansion decisions that when used in the second-stage, a set of flow variables can be found that satisfies all the demands without violating capacity constraints.
The first result is straightforward. From equations \ref{eq:hist28} and \ref{eq:hist29}, we have $\sum_{l\in L_{e}} \hat{z}_{e,l}=1$ \hspace{1mm} $\forall e\in E$. Therefore $\hat{z}$ is first stage feasible. As it is assumed that $\hat{z}$ is using the capacity expansion alternatives with maximum capacity for each link, the networks capacity cannot be increased using any other alternative. So if using $\hat{z}$, the network is not able to satisfy the demands without exceeding link capacities, it will not be able to do so using any other alternative either. Therefore, the problem would be infeasible. For the second result, note that by Lemma 1 we know that by using the highest capacity alternative for each link, we have implicitly chosen the costliest as well. Therefore $\hat{f}$ would be an upper bound on the objective function.

\paragraph{Example 3}  In the introductory example from chapter \ref{chap-two}, for links $e_{2}$ and $e_{3}$ from Table \ref{tab:three} we have $C_{2,2} > C_{2,1} $  and  $U_{2,2}\leq U_{2,1} $ and also $ C_{3,1} > C_{3,2} $  and  $ U_{3,1}\leq U_{3,2}$ . By Proposition 1 alternatives (2,2) and (3,1) can be removed from the model, resulting in  $z_{2,1}=1$ and $z_{3,2}=1$. For the remaining variables, highest capacities and costliest alternatives (represented by $\hat{z}$ and $\tilde{z}$, respectively) are chosen. So we have $\hat{z}=(0,1,1,0,0,1,1,0,1,0)$ with $\hat{f}$= 48, and $\tilde{z}=(0,1,1,0,0,1,1,0,1,0)$ with $\tilde{f}$= 48. As can be observed, the result of Lemma 1 holds for this case. As for Proposition 3, $\hat{z}$ is feasible and $\hat{f} \geq f^* $ $(48 \geq 36)$. There exists no other alternative with a higher cost for any of the links; therefore 48 is an upper bound for the objective function.

\begin{spacing}{1.5}
\paragraph{Proposition 4}
\textit{Suppose we create a failure scenario $\dot{s}$ such that}
\end{spacing}
\begin{equation}
\lambda_{e,\dot{s}}=\min_{s}\lambda_{e,s} \hspace{4mm}\forall e\in E
\label{eq:hist31}
\end{equation}
\textit{and}
\begin{equation}
\mu_{d,\dot{s}}=\max_{s}\mu_{d,s} \hspace{4mm}\forall d\in D
\label{eq:hist32}
\end{equation}
\begin{spacing}{1.5}\textit{and replace the second-stage problem of SNCE-1 by the capacity and demand constraints representing  $\dot{s}$. If the new problem has an optimal cost of $\dot{f}$, then $\dot{f}$ serves as an upper bound for the optimal cost of capacity expansion decisions in the SNCE-1 model. If the new problem is infeasible, no conclusions can be made. }
\end{spacing}
\vspace{5mm}
Proposition 4 suggests that if a worst case scenario ($\dot{s}$) that has minimum availability across all the scenarios for all the links and maximum value across all the scenarios for all the demands is created, then all the scenarios in SNCE-1 are removed and the problem is solved with scenario $\dot{s}$ only. Then the objective value of the new problem is an upper bound on the optimal cost of the original SNCE-1. Note that if such a scenario actually exists in the model, then based on Proposition 2 all the other scenarios can be removed from the problem as $\dot{s}$ dominates them all. In this case the upper bound represented by $\dot{s}$ would actually be the optimal cost as well. If such a worst case scenario does not exist in the problem, it can always be created using the problem data and equations \ref{eq:hist31} and \ref{eq:hist32}.
\paragraph \indent \textit{ \textbf{{Proof :}}}
From equations \ref{eq:hist31} and \ref{eq:hist32}, we have
\begin{equation}
\lambda_{e,\dot{s}} \leq \lambda_{e,s} \hspace{4mm}\forall e\in E \hspace{4mm}\forall s\in S
\label{eq:hist34}
\end{equation}
and
\begin{equation}
\mu_{d,\dot{s}} \geq \mu_{d,s} \hspace{4mm}\forall d\in D \hspace{4mm}\forall s\in S
\label{eq:hist35}
\end{equation}
Therefore the conditions for applying Proposition 2 ( equations \ref{eq:hist20} and \ref{eq:hist21}) are met. As a result all failure scenario are dominated by $\dot{s}$ and can be removed from the model. Suppose we formulate a new model by replacing all the failure scenario with single scenario of $\dot{s}$. Let us denote the new problem by SNCE-1-W. SNCE-1-W and SNCE-1 have the same first-stage variables and constraints, but based on Proposition 2, the second-stage constraints of SNCE-1-W dominate those of SNCE-1. Thus  $\dot{f} \geq f^*$, where $\dot{f}$ stands for the optimal objective of SNCE-1-W and $f^*$ is the optimal objective of SNCE-1. 
%As discussed earlier for the case that such a scenario as $\dot{s}$ exists in the problem $\dot{f} = f^*$. 
It is worth noting that if $\dot{f}$ exists (i.e., SNCE-1-W is feasible), then $\dot{f}$ is always less than or equal to $\hat{f}$, the bound introduced in Proposition 3, and therefore makes a better bound.

\paragraph{Example 4}Consider the network in \fref{fig:hist3}, with the travel demand data provided in Table \ref{tab:four}. The data regarding initial capacities, capacity expansion alternatives and failure scenarios are also provided in Tables \ref{tab:five} and \ref{tab:six}.
\begin{figure}

\centering

\includegraphics[width=0.4\textwidth]{Chapter-3/figs/Net3}

\caption{The network used in example 4}

\label{fig:hist3}

\end{figure}

\begin{table}

\caption{Example 4 : Demands}

\label{tab:four}

\begin{center}

\begin{tabular}{lccc}

\toprule

Demand & Amount($s_{0}$)  & Paths\\

\midrule

$d_{1}$ \textit{(a-c)}  & 6 & \textit{$p_{1}=(e_{1},e_{4}),p_{2}=(e_{3}), p_{3}=(e_{2},e_{5}), p_{4}=(e_{2},e_{6},e_{7})$}\\

$d_{2}$ \textit{(d-c)}  & 5 & \textit{$p_{5}=(e_{5}), p_{6}=(e_{6},e_{7})$}\\

$d_{3}$ \textit{(d-f)}  & 4 & \textit{$p_{7}=(e_{6},e_{8})$}\\

\midrule

\bottomrule

\end{tabular}

\end{center}

\end{table}
According to Proposition 1, $z_{3,1}=z_{4,3}=0$. Based on Proposition 2, $ s_{0}$ is being dominated by both $ s_{1}$ and $ s_{4}$ and therefore can be removed from the model. To calculate $\hat{f}$, the bound suggested by Proposition 3, the following variables should be fixed: $z_{1,3}=z_{2,3}=z_{3,3}=z_{4,1}=z_{5,3}=z_{6,3}=z_{7,3}=z_{8,3}=1$. The objective function value after solving the problem with the above conditions would be $\hat{f}=131$, which is an upper bound for the optimal objective value $f^*= 73$.


\begin{table}

\caption{Example 4 : Capacity Expansion Alternatives}

\label{tab:five}

\begin{center}

\begin{tabular}{l|c|cccccc}

\toprule

Link & Initial Cap. & Alt 1 Cap.  &Alt 1 Cost &Alt 2 Cap.  &Alt 2 Cost &Alt 3 Cap.  &Alt 3 Cost\\



\midrule

\textit{$e_{1}$} &6 &1 & 10 &5 & 15 & 17 & 18\\

\textit{$e_{2}$} &4 & 3 & 8 &1 & 9 & 21 &10\\

\textit{$e_{3}$} &4 &2 & 7 &3 & 5 & 9 & 10\\

\textit{$e_{4}$} &6 & 5 & 10 &2 & 8 & 3 & 17\\

\textit{$e_{5}$} &5 & 2 & 5 &1 & 2 & 31 & 8\\

\textit{$e_{6}$} &6 &6 & 9 &4 & 5 & 25 & 35\\

\textit{$e_{7}$} &5 & 5 & 11 &2 & 5 & 10 & 20\\

\textit{$e_{8}$} &6 & 5 & 13 &3 & 2 & 50 & 20\\

\midrule

\bottomrule

\end{tabular}

\end{center}

\end{table}
\begin{table}

\caption{Example 4 : Failure Scenarios}

\label{tab:six}

\begin{center}

\begin{tabular}{lcc}

\toprule

Scenario & Coefficients of Links Availability & Coefficients of Demand \\



\midrule

\textit{$s_{0}$} &(1,1,1,1,1,1,1,1) & (1,1,1)\\

\textit{$s_{1}$} &(0.90,0.55,0.48,0.82,0.69,0.32,0.58,0.50) & (2.0,1.4,1.9)\\

\textit{$s_{2}$} &(0.44,0.76,0.55,0.64,0.46,1.00,0.74,0.87) & (0.8,0.5,1.6)\\

\textit{$s_{3}$} &(0.66,0.42,0.17,0.36,0.69,0.43,0.71,0.54) & (0.6,0.6,2.1)\\

\textit{$s_{4}$} &(0.15,0.82,0.45,0.61,0.63,0.55,0.69,0.97) & (1.0,1.1,1.7)\\




\midrule

\bottomrule

\end{tabular}

\end{center}

\end{table}

To illustrate Proposition 4, scenario $\dot{s}$ is created with $\lambda_{\dot{s}}$=(0.15, 0.42, 0.17, 0.36,0.46, 0.32, 0.58, 0.50 ) and $\mu_{\dot{s}}$=(2.0, 1.4, 2.1). Then the new scenario $\dot{s}$ replaces all the other scenarios. $\dot{f}$, the objective function of the new problem equals 73, which is equal to the optimal value of the objective function value of the original problem, thus as claimed $f^*\leq \dot{f} \leq \hat{f} $ . 
%It is noted that the model solved to calculate $\dot{f}$ has 19 variables as opposed to 63 constraints in the original problem.\\\\\\\\\\\\

\subsection{Lower Bounds on the Cost Function}
In this section we introduce and discuss a few lower bounds on the optimal cost of capacity expansion decisions in the SNCE-1 problem.

\begin{spacing}{1.5}
\paragraph{Proposition 5}
\textit{Suppose we create a failure scenario $s_{b}$ such that}
\end{spacing}
\begin{equation}
\lambda_{e,s_{b}}=\max_{s}\lambda_{e,s} \hspace{4mm}\forall e\in E
\label{eq:hist36}
\end{equation}
\textit{and}
\begin{equation}
\mu_{d,s_{b}}=\min_{s}\mu_{d,s} \hspace{4mm}\forall d\in D
\label{eq:hist37}
\end{equation}
\begin{spacing}{1.5}
\textit{and replace the second-stage problem of SNCE-1 by the capacity and demand constraints representing  $s_{b}$. If the new problem has an optimal cost of $f_{b}$, then $f_{b}$ serves as a lower bound for the optimal cost of capacity expansion decisions in the SNCE-1 problem. If the new problem is infeasible, then SNCE-1 will also be infeasible . }
\end{spacing}
\vspace{5mm}
Proposition 5 discusses the opposite idea of Proposition 4. It suggests that if a scenario ($s_{b}$) is created with maximum availability across all the scenarios for all the links and minimum value across all the scenarios for all the demands. Then this scenario replaces all the other scenarios of SNCE-1. The optimal objective value of the new model is then a lower bound on the optimal cost of the original SNCE-1. If the new model is infeasible, then the original SNCE-1 would also be infeasible. Note that if such a scenario actually exists in the problem, then according to Proposition 2, it will be dominated by any other scenario.

\paragraph \indent \textit{ \textbf{{Proof :}}}

From equations \ref{eq:hist36} and \ref{eq:hist37} we have
\begin{equation}
\lambda_{e,s_{b}} \geq \lambda_{e,s} \hspace{4mm}\forall e\in E \hspace{4mm}\forall s\in S
\label{eq:hist38}
\end{equation}
and
\begin{equation}
\mu_{d,s_{b}} \leq \mu_{d,s} \hspace{4mm}\forall d\in D \hspace{4mm}\forall s\in S
\label{eq:hist39}
\end{equation}
By Proposition 2, any of the failure scenarios qualify for dominating $s_{b}$. Therefore as it is representing looser constraints, $s_{b}$ can be removed from the model without affecting the optimal solution. This implies that at least enough capacities should be allocated to the links to meet the demand and capacity constraints of $s_{b}$. This argument makes $f_{b}$, the optimal objective function value of the model solved with $s_{b}$ as the only failure scenario, a lower bound for the optimal cost of SNCE-1. If the model with single failure scenario of $s_{b}$ is infeasible, it is implied that the network is not even able to meet the demand and capacity constraints looser than its original constraints; thus the original problem is also infeasible.

\paragraph{Example 5}Again, consider the network illustrated in \fref{fig:hist3} and discussed in Example 4. Now suppose the failure scenario $s_{0}$ does not exist, i.e., network faces only scenarios $s_{1}$ to $s_{4}$. To illustrate Proposition 5, scenario $s_{b}$ is created with $\lambda_{s_{b}}=(0.9, 0.82, 0.55, 0.82, 0.69, 0.55, 0.74, 0.97)$ and $\mu_{s_{b}}=(0.6, 0.5, 1.0)$. $f_{b}$, the optimal cost of capacity expansion for the network in \fref{fig:hist2} with the single failure scenario of $s_{b}$, is equal to 5, which is an upper bound for the optimal cost of the original problem (73). As can be seen this bound is rather loose and is not providing good information regarding the actual optimal cost.

\begin{spacing}{1.5}
\paragraph{Lemma 2}
\textit{Solving the SNCE-1 problem with each one of the failure scenarios provide a lower bound for the optimal cost of the original problem.}\\
\end{spacing}

Suppose SNCE-1-i is formulated using SNCE-1 problem, by dropping all the capacity and demand constraints except the ones representing failure scenario \textit{i}. Lemma 2 suggests that for all $\textit{i}$ $\in$ $1...|S|$, the optimal value of the objective function ($f_{i}$) of SNCE-1-i, serves as a lower bound for the optimal objective function value of SNCE-1.
\paragraph \indent \textit{ \textbf{{Proof :}}} As the problem is an instance of a survivable network capacity expansion problem, the network should meet the demand and capacity constraints of all the failure scenarios. Let us denote the feasible region of SNCE-1 by $K$ and the feasible region of scenario $s$ by $K_{s}$, where $K =  \left\{\cap_{i} \text{ }K_{i}\text{ } | \text{ }i\in S \text{ } \right\}$. Therefore $K \subset K_{i}\text{ }, i  \in S $. The objective functions of SNCE-1 and SNCE-1-i are exactly the same and the feasible region of SNCE-1 is a subset of the feasible region of SNCE-1-i. Therefore, it can be concluded that the optimal objective function value of SNCE-1-i is always less than or equal to the optimal objective function value of SNCE-1. Hence the optimal objective function value of SNCE-1-i serves as a lower bound for the optimal cost of capacity expansion decisions in SNCE-1.

\paragraph{Example 6} Consider the network illustrated in \fref{fig:hist3} and discussed in Example 5. The optimal cost of capacity expansion decisions for this network is 73. The lower bounds suggested by scenarios 0 to 4 are 0, 73, 7, 55 and 47, respectively. For this example the number of second-stage constraints reduces from 55 to 11. In general the number of the second-stage constraints necessary to calculate the bound provided by each scenario would be $(|E|+|D|)$ . \\\\


\section{Decomposition Approach}
Because of the potentially large number of variables and constraints in SNCE-1, taking advantage of the model structure is important and helpful. The special structure of SNCE-1 allows us to apply a decomposition scheme to solve the model. Benders decomposition is a classical solution approach to solving two-stage linear programs. This method partitions the model into simpler problems; one master problem and several sub-problems. In this section we describe a decomposition approach, based on Benders decomposition, for solving survivable network capacity expansion problem. We start by describing the structure of the master and sub-problems, and then present the solution methodology.
\subsection{The Master Problem}
The idea is to solve a sequence of successively stronger relaxations of SNCE-1, where each relaxation is obtained from the previous one by adding feasibility cuts that were being violated by the previous optimal solution. The relaxation that gets successively stronger is called the master problem, and the problems which are being re-formulated and solved to get the feasibility cuts are called sub-problems. We consider our first-stage problem as the master problem. Therefore the master problem would be a mixed integer linear model with binary capacity expansion variables $z$ and mutual exclusion constraints. The model formulation for the master problem is described below.\\

\textbf{Master Problem (SNCE-1-M)}

\begin{equation}
  Min \sum_{e\in E}\sum_{l\in L_{e}}C_{e,l} \hspace{1mm}z_{e,l}
  \label{eq:hist40}
\end{equation}
\begin{spacing}{0.75}
\hspace{15mm} \textit{subject to.}
 \begin{center}
 \begin{equation}
 \sum_{l\in L_{e}} z_{e,l} \leq 1 \hspace{10mm} \forall e=1,2,...,|E|  \label{eq:hist41}
\end{equation}
\begin{equation}
 z_{e,l}\in \left\{0,1\right\}\hspace{5mm} \forall e=1,2,...,|E| \hspace{2mm} \forall l=1,2,...,|L_{e}|  \label{eq:hist42}
\end{equation}
\end{center}
\end{spacing}
\begin{spacing}{2.5}
\end{spacing}

This formulation is the initial master problem, with no additional cuts. As can be observed, this pure integer (binary) problem has a trivial optimal solution of zero (all variables are equal to zero, as there is no demand or capacity constraint present).

\subsection{The Sub-Problems}
The second-stage problem of SNCE-1 can be considered as separate scenario-based sub-problems. This special structure allows us to decompose the second-stage problem by the failure scenario to create the sub-problems for the decomposition approach. Each sub-problem would be formulated by fixing the first-stage variables at the values computed by solving the master problem. Any one of the sub-problems would be representing capacity and demand constraints of one of the failure scenarios. The objective function value of all the sub-problems would be zero (recall that in Chapter \ref{chap-two} we assumed once sufficient capacity is installed, routing the flows does not add to the cost ). The sub-problem representing Scenario $s_{1}$ can be written as follows :\\\\
\textbf{Sub-Problem (SNCE-1-S)}

\begin{equation}
Min \hspace{5mm} 0
  \end{equation}
\begin{spacing}{0.75}
\hspace{15mm} \textit{subject to.}
 \begin{center}
\begin{equation}
 \lambda_{e,s_{1}}\left(U_{e,0}+\sum_{l\in L_{e}}U_{e,l} \bar{z}_{e,l}\right)-\sum_{d\in D}\sum_{p\in P_{d}}k_{e,p_{d}}x_{p,s_{1}}\geq 0 \hspace{5mm} \forall e=1,2,...,|E| \hspace{2mm}   \label{eq:hist43}
\end{equation}
\begin{equation}
\sum_{p\in P_{d}}x_{p,s_{1}}-\mu_{d,s_{1}}h_{d}\geq 0 \hspace{5mm} \forall d=1,2,...,|D| \hspace{2mm} \label{eq:hist44}
\end{equation}
\begin{equation}
 x_{p_{d},s_{1}}\geq 0 \hspace{5mm} \forall p=1,2,...,|P_{d}|; \hspace{2mm} \forall d=1,2,...,|D| \hspace{2mm} \label{eq:hist45}
\end{equation}
\end{center}
\end{spacing}
\begin{spacing}{2.5}
\end {spacing}
where $\bar{z}$ is the capacity expansion decisions from solving the master problem, which is being used as a fixed parameter to formulate the sub-problem. Note that the sub-problems are being used as feasibility tests for the specific capacity expansion decisions. Capacity expansion decision $\bar{z}$ is feasible if and only if there exists a set of flow variables ($\bar{x}_{p_{d}}$) that satisfies the capacity and demand constraints for all $s\in S$. As all the sub-problems have an objective function of zero, they can be considered as pure allocation problems.
Sub-problems can be reformulated using an extra variable, representing the maximum overload flow on links. Therefore each failure scenario the flow allocation problem would be : \\\\
\textbf{Reformulation of Sub-Problems (SNCE-1-R)}
\begin{equation}
Min \hspace{5mm} \omega_{1}
\label{eq:hist46}
  \end{equation}
\begin{spacing}{1}
\hspace{15mm} \textit{subject to.}
 \begin{center}
\begin{equation}
 \omega_{1}+ \lambda_{e,s_{1}}\left(U_{e,0}+\sum_{l\in L_{e}}U_{e,l} \bar{z}_{e,l}\right)-\sum_{d\in D}\sum_{p\in P_{d}}k_{e,p_{d}}x_{p,s_{1}}\geq 0 \hspace{5mm} \forall e=1,2,...,|E| \hspace{2mm}   \label{eq:hist47}
\end{equation}
\begin{equation}
\sum_{p\in P_{d}}x_{p,s_{1}}-\mu_{d,s_{1}}h_{d}\geq 0 \hspace{5mm} \forall d=1,2,...,|D| \hspace{2mm} \label{eq:hist48}
\end{equation}
\begin{equation}
 x_{p,s_{1}}\geq 0 \hspace{5mm} \forall p=1,2,...,|P_{d}|; \hspace{2mm} \forall d=1,2,...,|D| \hspace{2mm} \label{eq:hist49}
\end{equation}
\begin{equation}
 \omega_{1} \geq 0
 \label{eq:hist50}
\end{equation}
\end{center}
\end{spacing}
\begin{spacing}{2.5}
\end {spacing}
If the optimal objective function value of SNCE-1-R is zero for all $s\in S$, then $ \bar{z} $ is feasible with respect to all the failure scenarios.

\subsection{Constructing Feasibility Cuts}

As discussed in the previous section, SNCE-1-R is used as a feasibility test for $ \bar{z} $. The test is successful if using $ \bar{z} $, there exists a set of feasible flow variables with no overload on the links. i.e., for all the failure scenarios the optimal solution to SNCE-1-R is zero. In the decomposition approach, if the test is not successful for a specific scenario, a feasibility cut for that specific failure scenario is generated and added to the master problem. Here we discuss how these cuts are generated for each scenario. The dual problem of SNCE-1-R is as follows :\\\\

\textbf{Dual of reformulated sub-problem (SNCE-1-R-D)}
\begin{equation}
Max \sum_{d}\chi_{d}h_{d} -\sum_{e}\pi_{e}\lambda_{e,s_{1}}\left(U_{e,0}+\sum_{l\in L_{e}}U_{e,l}\bar{z}_{e,l}\right)\hspace{5mm}
\label{eq:hist51}
  \end{equation}
\begin{spacing}{1}
\hspace{15mm} \textit{subject to.}
 \begin{center}
\begin{equation}
\sum_{e}\pi_{e}=1
    \label{eq:hist52}
\end{equation}
\begin{equation}
 -\sum_{e} k_{e,p_{d}}\pi_{e} + \chi_{d} \leq 0\hspace{5mm}  \hspace{4mm} \forall d=1,2,...,|D| \hspace{2mm} \forall p=1,2,...,|P_{d}| \hspace{2mm} \label{eq:hist53}
\end{equation}
\begin{equation}
\pi_{e}\geq 0 \hspace{5mm} \forall e=1,2,...,|E| \hspace{2mm} \label{eq:hist54}
\end{equation}
\begin{equation}
\chi_{d}\geq 0 \hspace{5mm} \forall d=1,2,...,|D| \hspace{2mm} \label{eq:hist55}
\end{equation}
\end{center}
\end{spacing}
\begin{spacing}{2.5}
\end{spacing}
where $\pi_{e}\hspace{0.5mm} , e\in E $ are dual variable of constraints in equations\ref{eq:hist47} and $\chi_{d}\hspace{0.5mm} , d\in D $ are dual variables of constraints in equation \ref{eq:hist48}.
From the strong duality theorem we have :

\begin{equation}
\omega_{1}^* \geq \sum_{d}\chi^*_{d}h_{d} -\sum_{e}\pi^*_{e}\lambda_{e,s_{1}}\left(U_{e,0}+\sum_{l\in L_{e}}U_{e,l}\bar{z}_{e,l}\right)\hspace{5mm}
\label{eq:hist56}
  \end{equation}
  If the feasibility test is successful, we get $ w_{1}^* \leq 0$. Therefore if the test for Scenario $s_{1}$ is feasible, then we would have :
  \begin{equation}
0 \geq \omega_{1}^* \geq \sum_{d}\chi^*_{d}h_{d} -\sum_{e}\pi^*_{e}\lambda_{e,s_{1}}\left(U_{e,0}+\sum_{l\in L_{e}}U_{e,l}\bar{z}_{e,l}\right)\hspace{5mm}
\label{eq:hist57}
  \end{equation}
 Therefore, if the feasibility test of the scenario fails, it means that the following inequality is being violated by the current optimal solution and it should be added to the master problem as a cut.
 \begin{equation}
0 \geq  \sum_{d}\chi^*_{d}h_{d} -\sum_{e}\pi^*_{e}\lambda_{e,s_{1}}\left(U_{e,0}+\sum_{l\in L_{e}}U_{e,l}z_{e,l}\right)\hspace{5mm}
\label{eq:hist58}
  \end{equation}
\subsection{Decomposition Algorithm}

SNCE-1 model is solved using decomposition method, as described in the previous sections. The method proceeds by solving the master problem and scenario sub-problems iteratively. At each iteration $ v $ of the method, a set of first-stage capacity expansion decisions, $z^v$, is found and sent to the scenario sub-problems. Using this solution, each sub-problem is solved. If the sub-problem has an optimal objective of greater than zero, a feasibility cut will be generated using \ref{eq:hist58} and added to the master problem. The algorithm terminates iterating when a first-stage solution that is feasible with respect to all the failure scenarios is found.\\\\
\textbf{Decomposition Algorithm for SNCE-1}

\begin{enumerate}
\item $n = 1$
\item Start with an arbitrary solution vector $ z_{0}$ to the master problem
\item \textbf{While} $ n \leq|S| $  \textbf{do}
{\setlength\itemindent{15pt} \item   $subProblemInfeasibility=1$ }
{\setlength\itemindent{15pt} \item  \textbf{While} $subProblemInfeasibility=1$  \textbf{do}
 \begin{enumerate}

{\setlength\itemindent{25pt}
 \item Compute the objective function of sub-problem $n$ , $\omega_{n}$ , using ( \ref{eq:hist51} to \ref{eq:hist55})


 \item If $\omega_{n} > 0 $ then $subProblemInfeasibility=1$ else $subProblemInfeasibility=0$

 \item If $subProblemInfeasibility=1$ then
      \begin{enumerate}
       {\setlength\itemindent{45pt}

	         \item  add feasibility cut (\ref{eq:hist58}) to the master problem
             \item Solve the update master problem
             \item Update $z$
             }
	  \end{enumerate}

	}
\end{enumerate}
}
{\setlength\itemindent{25pt}
\item $ n = n+1 $ }
\item Return $z$

	
	
 \end{enumerate}
%In Appendix A, we provide the code for implementing the decomposition algorithm. Furthermore the data set representing network 1 is provided in Appendix B.













